1. Field of the Invention
The present invention is related to data transfer operations in a computer system and more specifically, to arbitration of transfer resources for data transfer operations in a computer system.
2. Art Background
In a computer system, a transfer resource such as a bus or a buffer can be shared pathway bridging between two or more devices. Although data in a resource may be available to all attached devices, only one device should be allowed to transmit data into the resource in order to have a valid transmission. Because more than one device may need control of the resource at a given time, a systematic and efficient methodology of resolving contentions among multiple requesting devices plays a crucial role in the success of the computer system.
Modern computer systems commonly have arbitration schemes with either fixed or rotating priority-based controllers, i.e. arbiters, to resolve resource contentions. In a fixed priority system, each requesting device is given a rank in a hierarchy: when two or more devices are active, the highest ranked device is granted first, and others will follow in sequence of decreasing rank. Although contentions are resolved, the rigidity of a fixed priority scheme often leads to the problem of starvation: the low priority requesters may be excluded from using the resource if high priority devices alternate with their control of the resource. Also, from a system utilization perspective, if a high priority device's operation is suspended because resources down the transfer pathway are unavailable, the low priority devices should be allowed to use the resource to prevent system idling. In this respect, the fixed priority system fails to provide for such an occurrence.
In a rotating priority system, the control of a resource is routed through all possible requesters by issuing a token in either a round robin or random order. A requester can only gain control of the resource when the token is received. Although each device is given an access right to the resource, a system can still be forced to idle when device A cannot complete its operation due to unavailability down the pathway, and the next-in-line device B does not get the token. As in the fixed priority scheme, the rotating priority system cannot provide efficient resource utilization and high operation band-width.
The shortcomings in the fixed and rotating priority systems are exacerbated when a resource is simultaneously handling multiple-channel data transfers, as in the case of direct memory access ("DMA") operations. DMA is an efficient technique for transferring large volumes of data among devices and memory in that the central processing unit ("CPU") can be freed up from the straightforward transfer operation. To transfer data, a DMA controller must gain control of the bus or buses. When there are multiple channels of transfer requested by various devices attached to the DMA controller, the latter should be able to service the channels in a time-multiplexing fashion to achieve system efficiency. In other words, one device should not hold up one or more resources while waiting for the remaining resources to become available. In that sense, a DMA controller itself can be viewed as a resource to be shared among the requesting devices and such sharing must be efficient and fair. A DMA transfer operation easily requires multiple resources such as buses and buffers to complete. However, with a fixed or rotating priority system, the DMA controller must observe the rigid priority scheme even though the other necessary resources are not available for a requester to complete the operation. There is no mechanism for the controller to skip to the next requester capable of completing the transfer while the first requester is waiting for its resources to become available.
As will be described in the following, the present invention discloses a method and apparatus for arbitrating among a plurality of requesting devices based on the availability of transfer resources with respect to completing the requested transfer. As will be apparent from the following description, the present invention provides an intelligent arbitration based on an evaluation of the transfer resources with respect to the requested operation so that the system can achieve efficient utilization.